package Link;

import java.util.ArrayList;
import java.util.List;

public class leet_143 {

}

class Solution_143 {
    public void reorderList(ListNode head) {
        linerNode(head);

    }

    public void linerNode(ListNode head){
        List<ListNode> node = new ArrayList<>();
        ListNode curr = head;
        while(curr!=null){
            node.add(curr);
            curr=curr.next;
        }
        // 重构链表
        int left = 0;
        int right = node.size()-1;
        // 头-尾 -头-尾 - 头-尾 - 头-尾
        while(left<right){
            // 第一步 left指向right
            // 第二步 right 指向left+1
            // 第三步 right-1 指向null
            // 第四步 left++ right--
            // 特殊情况是链表为双数中间的是不需要发生改变
            if(left+1 == right){
                break;
            }
            node.get(left).next = node.get(right);
            node.get(right).next = node.get(left+1);
            node.get(right-1).next = null;
            left++;
            right--;
        }
    }

}

